
// 1027.最长等差数列
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        // 使用一个DP表来实现
        // 要使用一个二维DP表来完成
        int n = nums.size();
        
        vector<vector<int>> dp(n,vector<int>(n,2));
        unordered_map<int,int> m;
        int ret = 2;
        m[nums[0]] = 0;
        for(int i = 1 ; i < n ; i++)            // 枚举倒数第二个位置
        {
            for(int j = i + 1 ; j < n ;j ++)    // 枚举倒数第一个元素
            {
                int a = 2*nums[i] - nums[j];    // 找倒数第三个元素    
                if(m.count(a) && m[a] < i)
                    dp[i][j] = dp[m[a]][i] + 1;
                ret = max(ret , dp[i][j]);
            }
            m[nums[i]] = i;
        }
        return ret;
    }
};